# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
# 
# You should have received a copy of the GNU General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.

import itertools

from patrick_chapter_2_hw_1 import *
from fractions import Fraction
from copy import copy

def buchberger(ideal):
    """Basic implementation of Buchberger's algorithm for calculating a
    Groebner basis. Implemented with no improvements."""
    groebner = ideal
    groebner_loop = list()

    while groebner != groebner_loop:
        groebner_loop = groebner

        for pair in itertools.combinations([groebner_loop], 2):
            s = s_polynomial(pair[0][0], pair[0][1])
            if not zero_polynomial(s):
                groebner.append(s)

    return groebner

def s_polynomial(f, g):
    """See Cox, Little, O'Shea, pg. 81 for more details.

    Calculates the S-Polynomial:
    S(f, g) = \frac{x^\gamma}{LT(f)} \times f - \frac{x^\gamma}{LT(g)} \times g"""
    if len(f.leading_term().degrees) != len(g.leading_term().degrees):
        raise Exception("Polynomials not of same variables!")

    f_degrees = f.leading_term().degrees
    g_degrees = g.leading_term().degrees

    y = []
    for i in range(len(f.leading_term().degrees)):
        y.append(max([f_degrees[i], g_degrees[i]]))

    xy = Monomial((Fraction(1), tuple(y)))

    s_f_monomial = divide_monomials(xy, f.leading_term())
    s_g_monomial = divide_monomials(xy, g.leading_term())

    s_f = multiply_polynomials(Polynomial([s_f_monomial]), f)
    s_g = multiply_polynomials(Polynomial([s_g_monomial]), g)

    return add_polynomials(s_f, s_g.negate())

if __name__ == "__main__":
    # x^3 - 2xy
    f_1 = Polynomial([(Fraction(1), (3, 0)), (Fraction(-2), (1, 1))])
    # x^2y - 2y^2 + x
    f_2 = Polynomial([(Fraction(1), (2, 0)), (Fraction(-2), (0, 2)), (Fraction(1), (1, 0))])
    # -x^3
    f_3 = Polynomial([(Fraction(1), (3, 0))])
    # -2xy
    f_4 = Polynomial([(Fraction(-2), (1, 1))])
    # -2y^2 + x
    f_5 = Polynomial([(Fraction(-2), (0, 2)), (Fraction(1), (1, 0))])

    g_basis = buchberger([f_1, f_2, f_3, f_4, f_5])

    print g_basis
